#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "unordered_set"
#include "queue"
using namespace std;
/*HJJ QQ479287006
 *
通过的用户数997
尝试过的用户数1478
用户总通过次数1001
用户总提交次数1968
题目难度Medium
给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。

你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。

请你返回 最少 需要划分成多少个组。

如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。



示例 1：

输入：intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
输出：3
解释：我们可以将区间划分为如下的区间组：
- 第 1 组：[1, 5] ，[6, 8] 。
- 第 2 组：[2, 3] ，[5, 10] 。
- 第 3 组：[1, 10] 。
可以证明无法将区间划分为少于 3 个组。
示例 2：

输入：intervals = [[1,3],[5,6],[8,10],[11,13]]
输出：1
解释：所有区间互不相交，所以我们可以把它们全部放在一个组内。
 https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/comments/
 * */
//就是求不同的排列数

//bool  isContain(vector<int> &source,vector<int> &dis)
//{
//    if (source[0]<dis[0]&&source[1]<dis[0] ||(source[0]>dis[1]))
//
//        return true;
//
//    if (dis[0]<source[0]&&dis[1]<source[0] ||(dis[0]>source[1]))
//
//        return true;
//
//    return false;
//
//}
//
//
//int minGroups(vector<vector<int>>& intervals,int )
//
//
//
////[[441459,446342],[801308,840640],[871890,963447],[228525,336985],[807945,946787],[479815,507766],[693292,944029],[751962,821744]]
//int minGroups(vector<vector<int>>& intervals) {
//
//
//    int index=0;
//    unordered_set<int> set_temp;
//
//    for (int i = 0; i <intervals.size() ; ++i) {
//
//
//        for (int j = i+1; j <intervals.size() ; ++j) {
//            if (set_temp.find(j)!=set_temp.end())
//                continue;
//
//            if (!isContain(intervals[i],intervals[j]))
//            {
//                index++;
//
//                break;
//            } else{
//                set_temp.insert(j);
//            }
//
//        }
//
//    }
//
//    if (set_temp.find(intervals.size()-1)==set_temp.end())
//        index++;
//
//
//    return index;
//}

//贪心：把所有区间按照左端点排序，然后遍历区间。对于当前区间的左端点，如果能找到一个最右端点
// 都触碰不到它的组，
// 就将这个区间并入那个组，然后更新这个组的最右端点；否则就需要开一个新的区间。因此，
// 我们需要用小根堆来维护之前每组区间的最右端点，最后堆中元素的数目就是最小组数。

//todo 哎我草 我不太明白这个优先级队列 确定把每次都找完了吗。。。我草我傻逼了 因为排序了 所以每次肯定都找完了
//int minGroups(vector<vector<int>>& intervals) {
//    int n = intervals.size();
//    sort(intervals.begin(), intervals.end());
//    priority_queue<int, vector<int>, greater<int>> heap;
//    heap.push(intervals[0][1]);
//    for(int i = 1; i < n; i++) {
//        int a=heap.top();
//        if(heap.top() >= intervals[i][0]) {
//            // 够得着之前组的某个右端点，需要开一个新的组
//            heap.push(intervals[i][1]);
//        }else {
//            // 否则将这个组并到堆顶区间所在的组
//            heap.pop();
//            heap.push(intervals[i][1]);
//        }
//    }
//    return heap.size();
//}

//15 110 23 510 68
//这是二刷了 有一点想不到 为什么push 新组后....唉你懂得
int minGroups(vector<vector<int>> &intervals) {
    sort(intervals.begin(), intervals.end());//先从小到大排序

    //利用优先级队列维护 一个组的最大右边界（注意这个是排序了

    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 0; i < intervals.size(); ++i) {
        //他得右边界
        if (!q.empty() && q.top() < intervals[i][0]) {
            q.pop();//先移除后添加
            q.push(intervals[i][1]);
        } else {
            q.push(intervals[i][1]);//添加一个新的分组

        }

    }

    return q.size();
}